/*
Permutations II Total Accepted: 41969 Total Submissions: 162769 My Submissions Question Solution
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

*/
#include <iostream>
#include "print.h"
#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
	void corepermuteUnqiue(vector<int>& nums, int index, vector<int> &perm, vector<vector<int> > &result)
	{
		int size = nums.size();
		if (size == index)
		{
			result.push_back(perm);
		}
		else
		{
			for (int i = index; i < size; i++)
			{
				if ((i > index) && (nums[i] == nums[index]))
				{
					continue;
				}
				else
				{
					swap(nums[index],nums[i]);
				}

				perm.push_back(nums[index]);
				corepermuteUnqiue(nums, index+1, perm, result);
				perm.pop_back();

			}

			sort(nums.begin() +index, nums.end());
		}
	}
	vector<vector<int> > permuteUnique(vector<int>& nums) {
		vector<vector<int> > result;
		vector<int> perm;

		sort(nums.begin(),nums.end());
		corepermuteUnqiue(nums,0,perm,result);
		return result;
	}
};


int main()
{
	int a[] = { 1, 1, 2 };
	vector<int> nums(a, a + sizeof(a) / sizeof(int));

	vector<vector<int> > res;
	Solution s;
	res = s.permuteUnique(nums);


	system("pause");
	return 0;
}